//给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。 
//
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
//输出：4 
//解释：最长递增路径为 [1, 2, 6, 9]。 
//
// 示例 2： 
//
// 
//输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
//输出：4 
//解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
// 
//
// 示例 3： 
//
// 
//输入：matrix = [[1]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 200 
// 0 <= matrix[i][j] <= 231 - 1 
// 
// Related Topics 深度优先搜索 广度优先搜索 图 拓扑排序 记忆化搜索 动态规划 
// 👍 496 👎 0

package leetcode.editor.cn;

/**
 * Java：矩阵中的最长递增路径
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P329_LongestIncreasingPathInAMatrix {
    public static void main(String[] args) {
        Solution solution = new P329_LongestIncreasingPathInAMatrix().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            int N = matrix.length;
            int M = matrix[0].length;
            // 最长的递增链
            int ans = 0;
            int[][] cache = new int[N][M];
            // 可以选择任意坐标开始
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    ans = Math.max(ans, process(matrix, i, j, cache));
                }
            }
            return ans;
        }

        /**
         * 从任意坐标i、j出发的最长递增链
         */
        private int process(int[][] arr, int i, int j, int[][] cache) {
            if (cache[i][j] != 0) {
                return cache[i][j];
            }
            int up = i - 1 >= 0 && arr[i - 1][j] > arr[i][j] ? process(arr, i - 1, j, cache) : 0;
            int down = i + 1 < arr.length && arr[i + 1][j] > arr[i][j] ? process(arr, i + 1, j, cache) : 0;
            int left = j - 1 >= 0 && arr[i][j - 1] > arr[i][j] ? process(arr, i, j - 1, cache) : 0;
            int right = j + 1 < arr[0].length && arr[i][j + 1] > arr[i][j] ? process(arr, i, j + 1, cache) : 0;
            int res = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
            cache[i][j] = res;
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}